package 剑指offer;

import leetcode.ListNode;

import java.util.*;

public class Offer_JZ27 {

    static ArrayList<String> res = new ArrayList<>();
    static Set<String> set = new HashSet<>();
    public static ArrayList<String> Permutation(String str) {
//        backtrack(str.toCharArray(), new ArrayList<Character>());
        boolean[] used = new boolean[str.length()];
        backtrack(str.toCharArray(), new StringBuilder(), used);
        return res;
    }

    public static void backtrack(char[] chars, StringBuilder stringBuilder, boolean[] used) {
//        if (list.size()==chars.length && !set.contains(list.toString())) {
//            set.add(list.toString());
//            res.add(list.toString());
//            return;
//        }
//
//        for (int i=0; i<chars.length; i++) {
//            list.add(chars[i]);
//            backtrack(chars, list);
//            list.remove(list.size()-1);
//        }

        if (stringBuilder.length()==chars.length && !set.contains(stringBuilder.toString())) {
            set.add(stringBuilder.toString());
            res.add(stringBuilder.toString());
            return;
        }

        for (int i=0; i<chars.length; i++) {
            if (used[i]) continue;
            stringBuilder.append(chars[i]);
            used[i] = true;
            backtrack(chars,  stringBuilder, used);
            stringBuilder.deleteCharAt(stringBuilder.length()-1);
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        System.out.println(Permutation("aba").toString());
//        List<Character> list = new ArrayList<>();
//        list.add('a');
//        list.add('b');
//        System.out.println();
    }
}
